1. Field of the Invention
The present invention relates to the field of routing messages in a communications network, and in particular to increasing the throughput of a routing system.
2. Description of the Related Art
In recent years, there has been an exponential increase in the demand for bandwidth in communications networks. This increase is due to a variety of factors, including an increase in the number of users as the Internet moves towards becoming a mass communications medium, and an increase in bandwidth-intensive multimedia applications that integrate still images, video and speech with data. To keep up with this increasing demand, communications facilities must frequently be upgraded.
Data routers are critical components in data communications networks. Routers link physical networks along the path from a source node to a destination node. In a network employing packet switching, data packets are passed from router to router until they reach their final destination. This process is known as "next hop routing."
FIG. 1 illustrates a conventional communications network of the type that employs next hop routing. In this example, a router 100 couples three networks 102. Each network 102 includes at least one host computer 104. Software in the router 100 implements an Internet protocol (IP) routing algorithm that determines how to send an IP datagram across the networks. The Internet protocol operates at layer 3 of the well-known layered OSI standard. For a host 104 to transfer an IP datagram to another host 104, the sender encapsulates the datagram in a physical frame ("packet"), wherein the destination IP address is mapped to a physical (layer 2) address. If the source and destination hosts lie within the same physical network, such as an Ethernet, then the source can send the datagram directly to the destination over the physical network.
FIG. 2 illustrates the format of an IP datagram 200 encapsulated in a physical frame 202. The frame 202 includes a frame header 204 followed by frame data 206 and a cyclic redundancy check code 208. The IP datagram 200, which is encapsulated as frame data 206, includes a datagram header 210 and datagram data 212.
FIG. 3 illustrates the format of a physical frame header 204, such as an Ethernet frame header. The frame header 204 includes a preamble 300, a destination address 302, a source address 304, and a frame type field 306. The preamble is employed for synchronization purposes. The destination address 302 contains the physical (layer 2) address of the destination node, which is unique to each hardware unit and is hard-coded into the hardware at the time of manufacture. The source address 304 is the physical address of the source node.
FIG. 4 illustrates the format of an IP datagram header 210, showing only fields that are relevant to the present invention. The fields include a time to live field 400, an IP source address 402, and an IP destination address 404. For further information regarding frame formatting and networking in general, please refer to D. Comer, Internetworking With TCP/IP," Volume 1, Prentice-Hall, Third Edition, 1995, which is incorporated by reference herein.
If the source and destination lie in different networks, then the router is employed to effect the transfer. Both hosts and routers maintain IP routing tables to determine where to send a datagram based upon the IP destination address. Typically a routing table contains pairs (N, R), where N is the IP address of a destination network or host, and R is the IP address of the next router along the path to network or host N. In this manner, a router need not know the complete path to a destination node, only the next hop. The next hop in a machine's routing table must lie in a physical network to which the machine connects directly. To assure selection of the proper next hop, routers exchange routing tables to keep track of changes in network configuration.
After executing a routing algorithm to obtain the next hop IP address in response to the ultimate destination address of a datagram, the router passes the datagram and the next hop address to network interface software in the router responsible for the physical network over which the datagram must be sent. The network interface software binds the next hop address to a physical address, forms a frame using that physical address, places the datagram in the data portion of the frame, and sends the resulting frame to a second (next hop) router over the physical network linking the next hop router to the first router. This process continues until the datagram reaches a final router that is connected directly to the same physical network as the destination. At that point, the final router will deliver the datagram using direct delivery.
After using the next hop address to find a physical address, the network interface software discards the next hop address. If the host is sending a sequence of datagrams to the same destination address, this process of determining the next hop IP address and then the next hop physical address is repeated, even though it appears very inefficient. As is well known in the art, the binding between the next hop IP address and the physical address is not saved because of the philosophy underlying the Internet protocol. The protocol builds an abstraction that hides the details of one network layer from another, thereby maintaining the distinction between the IP and physical address layers.
Because router functions, such as exchanging routing tables and executing routing algorithms require the flexibility of software to react to a changing environment, these functions are implemented in software rather than hardware. Thus, the capacity of routers is limited to the capacity of the microprocessors and the software that implement the necessary algorithms.
In order to increase data throughput, some routers have been designed in hardware to overcome the limitations of software. For example, Rekhter describes systems that contain local forwarding tables in switches, known as "forwarding information bases." Each table entry includes an ultimate destination address and a next hop destination address. The forwarding information base is constructed from information contained in a "routing information base" that in turn is constructed from routing information received from the network. For further information please refer to Y. Rekhter, "Inter-domain routing: EGP, BGP, and IDRP," in M. Steenstrup, Routing in Communications Networks, First Edition, 1995, pp. 99-133. Forwarding tables are also employed in U.S. Pat. No. 5,566,170 issued to Bakke et al. These and all other references referred to herein are incorporated by reference herein.
Further, other hardware-accelerated routers cache next hop information. Although these hardware routers increase throughput, replacing existing routers with these advanced routers is an expensive proposition. The expense is not just the cost of the router itself, but the administrative costs incurred in configuring the new router and the cost of associated network downtime. Accordingly, it is desired to find a more cost-effective way of upgrading existing routing systems to increase data capacity.